package chapter02;

import java.util.Arrays;

public class NumTrees96 {
    /**
     * 记忆化搜索
     * process(start,end) 当前来到子树根节点 取值为[start,end]
     * 假设 当前根节点为i 左子树可以取值[start.i-1] 右子树可以取值[i+1,end]
     * 递归出口
     *  1).start>end
     *      return 1
     *  2).枚举根节点 res=0
     *      i->[start,end]
     *      res+=process(start,i-1)*process(i+1,end)
     *      return res
     *  递归过程会出现重复解 增加缓存dp[start][end]
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public int numTrees(int n) {
        int[][] dp=new int[n+1][n+1];
        for(int i=0;i<dp.length;i++){
            Arrays.fill(dp[i],-1);
        }
        return process(1,n,dp);
    }

    public int process(int start,int end,int[][] dp){
        if(start>end){
            return 1;
        }
        if(dp[start][end]!=-1){
            return dp[start][end];
        }
        int res=0;
        for(int i=start;i<=end;i++){
            res+=process(start,i-1,dp)*process(i+1,end,dp);
        }
        dp[start][end]=res;
        return dp[start][end];
    }
}
